This invention relates to data transmission using continuous error detection based on arithmetic coding.
Arithmetic coding, as used in this invention, differs considerably from other compression techniques such as prefix (Huffman) block codes. Arithmetic coding is also distinct from error control coding, which can be used to detect and rectify errors in computer operations. Arithmetic coding, generally, is a data compression technique, which sequentially encodes data or a data string by creating a code string which represents a fractional value on the number line between 0 and 1. The coding algorithm performs encoding/decoding by operations upon one data symbol per iteration. The algorithm deals with successively smaller intervals, and the code string lies in each of the nested intervals. The code-string length corresponding to the data string is equivalent to the number of bits necessary to represent the magnitude of the interval in which the code-string falls. The data string of information is recovered by using magnitude comparisons on the code-string to recreate how the encoder must have successively partitioned and retained each nested subinterval.
The use of block cyclic redundancy check (CRC) is known as a popular and powerful error detection technique in modem digital communications.
However, though efficient, CRCs can detect errors only after an entire block of data has been received and processed. This invention provides a new class of xe2x80x9ccontinuousxe2x80x9d error detection techniques, and shows its applicability in a variety of popular communication applications, including (a) data transmission based on Automatic Repeat Request (ARQ), and (b) (Serially) Concatenated Coding systems deploying an inner error-correction code and an outer error-detection code. The inventive approach is based on a popular source (entropy) coding technique, namely the arithmetic coder. The basic concept of continuous error detection based on arithmetic coding was first suggested by Boyd, et al. in a paper entitled xe2x80x9cIntegrating Error Detection into Arithmetic Codingxe2x80x9d by C. Boyd, J. Cleary, S. Irvine, I. Rinsma-Melchert, and I. Witten, in IEEE Transactions on Communications, vol. 45, no. 1, Jan. 1997, albeit with little system performance analysis or exposition of its utility in communication systems. This invention presents a more rigorous analysis of this paradigm, quantifying the underlying tradeoffs involved in the process, but also establishes the impressive gains in system performance that are attainable through sophisticated integration of this novel paradigm into popular, powerful transmission applications such as those listed above.
There are several US patents which generally and severally relate to data coding, ARQ, and CRC in data transmission applications.
U.S. Pat. No. 5,530,708 to Miya teaches an error detection in data wherein the data is attached with error detection codes and then subjected to convolutional coding. The input data in Miya is subsequently subjected to an error correction Viterbi decoding operation, whereby at the time of detecting an error in the error detection code, an error detection block which has an error present therein is also detected.
U.S. Pat. No. 4,149,142 to Kageyama et al. teaches a selective automatic Request repeat (ARQ) system for controlling errors occurring in transmission of data on telephone data communication channels. Therein, an error controlling signal is devoid of a check bit for detection or correction of errors, thus obviating time loss which would occur if an error control signal was repeatedly issued between the transmission and receiving sides. The Kageyama system is useful in static image transmission.
In U.S. Pat. No. 5,715,257 to Matsuki et al., a selective repeat ARQ system with limited buffer memory is obtained by modifying a part of a user data area in a data frame. A comparison is made between a modified and an unmodified version of the user data area from the same frame number, and said part of the user data is preferably the last word area in a user data area in a frame structure.
U.S. Pat. No. 4,276,646 to Haggard et al. teaches method an apparatus for detecting errors in a data set of sequential binary digits. Initially, alternating ones of the binary digits are separated into data subsets to generate a CRC for each data subset. The code subsets are merged into a codeset. Depending on the form of the CRC generator, the code subset CRC value will indicate the presence of an error and the error location.
U.S. Pat. No. 4,718,066 to Rogard is directed to data transmission between a satellite and land mobile terminals. The system encodes data in sets of blocks including redundant symbols and redundant blocks, and provides automatic retransmission of lost data blocks, and in parallel, correction of detected errors within received blocks.
IEEE publication, xe2x80x9cIntegrating Error Detection into Arithmetic Codingxe2x80x9d by C. Boyd, J. G. Cleary, S. A. Irvine, I. Rinsma-Melchert, and I. H. Witten in IEEE Transactions on Communication, vol. 45, no. 1, Jan. 1997, teaches integrating error detection into arithmetic coding. In the publication, there is a discussion of why arithmetic coding can be used for error control. The publication states that with arithmetic coding, (a) the amount of redundancy included in the encoded message can be controlled as a single tunable parameter of the coding processing, and (b) error checking can take place continuously as each input bit is processed so that errors are located quickly. As per the IEEE publication, redundancy is introduced by adjusting the coding space so that some parts are never used by the encoder. During decoding, if the number defined by the received encoded string ever enters the forbidden region, a communication error must have occurred. To adjust the coding space, at regular points in the encoding procedure, the current coding interval is reduced by a certain proportion, which is called the xe2x80x9creduction factorxe2x80x9d. Upon decoding, the same reduction process is performed. The number defined by the received string is checked after each reduction to see if it lies within the received interval. If not, an error has occurred. Redundancy is controlled by varying the xe2x80x9creduction factorxe2x80x9d. Another method of adding redundancy is to use an extra model with only two symbols, encoding one of them periodically, and signaling an error if the other is ever decoded. The publication also discusses choosing the reduction factor, guaranteeing detection of single bit errors, and the use of end of file markers.
An object of this invention generally, is to provide continuous error checking in the transmission of data from a transmitter to a receiver, wherein, there is no need to wait for error checking until a complete block of data is transmitted.
In one aspect, the invention resides in a method of data-transmission from a transmitter to a receiver using an arithmetic coder without using cyclic redundancy check codes, comprising adding a forbidden symbol, which occupies xcex5-th portion of a coding space to a data stream of said data to increase redundancy, said forbidden symbol not being meant to be coded, controlling said coding space as necessary to control the redundancy, tracking if said forbidden symbol is decoded at the receiver and using a presence of such forbidden symbol decoding for error detection in said data transmission, conveying a position of an error to the transmitter, and requesting a retransmission of n bits where n is related to a confidence level whereby continuous error detection in said data transmission is performed with automatic repeat request.
In another aspect, the invention provides a method of transmitting data with continuous error detection in a received data bitstream, using a serially concatenated coding scheme with an inner convolutional coder and outer error detection coder by employing Viterbi Algorithms (VA), comprising changing the VA to produce an ordered list of N most likely transmitted codewords for a list N VA, checking a list of N best survivor paths during transmission, and using continuous error detection code to eliminate invalid trellis paths whereby a number of survivor paths needed to be processed and stored in the list N VA is reduced as compared with a number of paths needed with block cyclic redundancy check, and, continuous error detection is still ensured.
In yet another aspect, the invention provides a method of transmitting data from a transmitter to a receiver using an automatic repeat request (ARQ) to obtain continuous error detection comprising the steps of: partitioning the data into packets and introducing into the partitioned data a forbidden symbol which is not intended to be normally transmitted, nor decoded at the receiver receiving the transmitted data and checking if a decoded version of the forbidden symbol exists, indicating a transmission error, deciding in which data packet said transmission error occurred, and initiating retransmission of a portion of the data packet where said error occurred, said portion being located after occurrence of the error whereby data transmission is made more efficient.
The invention also provides a system and apparatus for data transmission using arithmetic coding generally using methods as stated supra. The continuous error detection system of the present invention allows to prune some incorrect paths earlier than the end of the block, and thus, increase the probability that the correct path will survive.
Applicants have discovered that there is a controllable trade-off between the error detection capabilities and the amount of redundancy added. The amount of time it takes to decode the xe2x80x9cforbiddenxe2x80x9d symbol after the occurrence of an error is inversely related to the amount of redundancy added through the introduction of the forbidden symbol. The forbidden symbol is never encoded by the arithmetic coder, but occupies a non-zero measure on the set of 0-1.
The proposed framework in this invention allows for an efficient way to detect errors continuously in the received bitstream, by investing a controlled amount of redundancy in the arithmetic coding operation. Interestingly, a growing popular opinion hitherto in the image transmission over noisy channels has been to avoid using the arithmetic coder due to its well-known error-sensitivity. This invention shows that it is not only possible to overcome this drawback, but to actually exploit it to improve system performance. Further, as most state-of-the-art image coding algorithms have an arithmetic coding xe2x80x9clast stagexe2x80x9d for entropy coding, it becomes possible to physically integrate the source coding and channel coding tasks in the same device, namely, the arithmetic coder. In this invention, the basic idea consists in adding, to the list of data symbols to be arithmetically encoded, an extra xe2x80x9cforbiddenxe2x80x9d symbol that is never actually transmitted, but for which a controlled amount of probability space or coding space is reserved nonetheless (note that this increases the redundancy of the coded symbol stream). By increasing the amount of coding space that the forbidden symbol occupies, it is possible make statistical guarantees about where the errors may have occurred. That is, it is possible to isolate the location of the error in a statistical sense, to any desired confidence level, to the previous n bits (where n depends on the amount of invested excess redundancy and the desired confidence level).
The invention is clearly useful in communication scenarios like ARQ or concatenated coding systems having an error-detection xe2x80x9couterxe2x80x9d component. In an ARQ system, the utility comes from the ability to make statistical statements relating the time of error occurrence to the time of its detection, resulting in potential savings in the number of bits that need to be retransmitted when an error is detected. The invention teaches how to optimize the tradeoff between added redundancy and error-detection time to attain significant throughput gains. In a serially concatenated coding system using inner convolutional codes, the use of continuous error detection can likewise be useful to eliminate invalid trellis paths, leading to potential performance gains. The invention teaches how to exploit the continuous ability to dynamically prune inadmissible subpaths in a xe2x80x9clistxe2x80x9d Viterbi Algorithm, thereby increasing the likelihood of retaining the correct path in the final list. The approach herein significantly reduces the number of paths which have to be processed and stored in the list Viterbi Algorithm compared to the number of paths needed with block CRC detection for the same overall performance. Described hereinafter are a method and a system to achieve the gains for both ARQ and concatenated coding schemes, using both analytical methods and validating simulations that demonstrate the effectiveness of incorporating continuous error detection in the aforementioned applications.